\documentclass[E:/GsjzTle/main/main.tex]{subfiles}


\begin{document}

\begin{itemize}
\item
  按秩合并可配合路径压缩一起使用，复杂度为 \(\alpha(N)\)
\item
  \(\alpha(N)\) 为反阿克曼函数，它是一个比 \(\log N\) 增长得还要慢的函数
\item
  但是路径压缩不支持撤销，而按秩合并可以
\end{itemize}

\begin{lstlisting}
int far[N] , dep[N];
int find(int x)
{
	if(x == far[x]) return x;
	return find(far[x]); // 改为 far[x] = find(far[x]) 就可添上路径压缩
}
void Union(int x , int y)
{
	int tx = find(x) , ty = find(y);
	if(tx == ty) return ; 
	if(dep[tx] < dep[ty]) far[tx] = ty;
	else 
	{
		far[ty] = tx;
		if(dep[tx] == dep[ty]) dep[tx] ++ ;
	}
}
void init(int n)
{
	for(int i = 1 ; i <= n ; i ++) far[i] = i , dep[i] = 1;
}
\end{lstlisting}

\end{document}
